11490. Простые на интервале 2

Заданы два натуральных числа a и c. Найдите такое наименьшее натуральное число b, что количество простых чисел на промежутке [a; b] включительно равно c.

Вход. Два натуральных числа a и c (a, c ≤ 10⁶).

Выход. Выведите искомое наименьшее значение b.

Пример входа	Пример выхода
3 4	11

РЕШЕНИЕ

простые числа

Анализ алгоритма

Перебираем числа a, a + 1, a + 2, … . Подсчитываем среди них простые. Как только встретится c простых чисел, останавливаемся. Таким образом найдем наименьшее b, для которого на промежутке [a; b] имеется в точности c простых чисел.

Пример

На интервале [3; 11] имеется 4 простых числа: 3, 5, 7 и 11.

Реализация алгоритма

Функция IsPrime проверяет, является ли число n простым. Число 1 не является простым.

int IsPrime(int n)

{

if (n <= 1) return 0;

for (int i = 2; i <= sqrt(n); i++)

if (n % i == 0) return 0;

return 1;

}

Основная часть программы. Читаем входные данные.

scanf("%d %d", &a, &c);

Начинаем движение переменной b от a по возрастанию значений: a, a + 1, a + 2, … . В переменной cnt подсчитываем количество пройденных простых чисел. Как только оно станет равным c, выходим из цикла.

cnt = 0;

for (b = a; ; b++)

{

if (IsPrime(b)) cnt++;

if (cnt == c) break;

}

Выводим ответ.

printf("%d\n", b);